package cn.cxq.learning.math;

import org.junit.jupiter.api.Test;

import java.util.LinkedList;

/**
 * 剑指offer
 * 字符流中第一个不重复的字符
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：295778
 * 本题知识点： 字符串
 *  算法知识视频讲解
 * 题目描述
 * 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
 * 后台会用以下方式调用Insert 和 FirstAppearingOnce 函数
 * string caseout = "";
 * 1.读入测试用例字符串casein
 * 2.如果对应语言有Init()函数的话，执行Init() 函数
 * 3.循环遍历字符串里的每一个字符ch {
 * Insert(ch);
 * caseout += FirstAppearingOnce()
 * }
 * 2. 输出caseout，进行比较。
 * 返回值描述:
 * 如果当前字符流没有存在出现一次的字符，返回#字符。
 */
public class FirstAppearingOnce {

    // 改造 ： 由于ascii字符之后128个，用一个数组存即可
    LinkedList<Character> queue = new LinkedList<>();// 用来存出现一次的字符（按顺序）
    int[] times =new int[128];

    public void Insert(char ch) {
        if (times[ch] == 0) {
            queue.addLast(ch);
        } else {
            queue.remove(new Character(ch));
        }
        times[ch]++;
    }

    public char FirstAppearingOnce() {
        if (queue.isEmpty()) {
            return '#';
        } else {
            return queue.getFirst();
        }
    }

//    LinkedList<Character> queue = new LinkedList<>(); // 用来存出现一次的字符（按顺序）
//    LinkedList<Character> exits = new LinkedList<>(); // 用来保存原字符流
//
    @Test
    public void test() {
        Insert('g');
        System.out.println(FirstAppearingOnce());
        Insert('o');
        System.out.println(FirstAppearingOnce());
        Insert('o');
        System.out.println(FirstAppearingOnce());
        Insert('g');
        System.out.println(FirstAppearingOnce());
        Insert('l');
        System.out.println(FirstAppearingOnce());
        Insert('e');
        System.out.println(FirstAppearingOnce());
    }

//    public void Insert(char ch)
//    {
//        if (exits.contains(ch)) {
//            // queue.remove(ch); 这样会报越界异常。
//            if (queue.contains(ch)) {
//                queue.remove(new Character(ch));
//            }
//            exits.addLast(ch);
//        } else {
//            queue.addLast(ch);
//            exits.addLast(ch);
//        }
//    }
//    //return the first appearence once char in current stringstream
//    public char FirstAppearingOnce()
//    {
//        if (queue.isEmpty()) {
//            return '#';
//        } else {
//            return queue.getFirst();
//        }
//    }
}
